package seqlist.LeetCode;
//82. 删除排序链表中的重复元素 II
//给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

/**
 * 思路一：虚拟头节点 + 三指针。之前我们删除一个链表都是找前驱，但现在头结点也有可能会是重复元素改怎么办？
 * 可以创建一个虚拟头节点，使得每个节点都具备头节点。那边怎么知道一个数是否是重复元素？
 * 可以用两种指针来比较node1和node2，当他们相等时，肯定就是了。但要求的是一个重复元素都
 * 不留，两个指针都用来判断的，改怎么删除节点呢？可以再创建 一个指针prve（前驱）来串联所有
 * 正确的节点
 */
//上下两个思路是一样的，看看留个印象
/**
 * 思路：要求是重复节点一个都不留，我们之前单链表的删除都是通过
 * 前驱节点删除 =》 现在第一个节点就有可能会是重复节点了，
 * 要保证 prve 坚决不能能带删除的节点，我们可以引用
 * 虚拟头节点的概念，如果不增加一个空节点来做，那么题目会变的非常的复制难办。
 * 但现在我们还需要 两个指针来判断是否为 重复数，那就再引入 node1，node2
 */
//注释：一定要先判断node2 != null 用while循环到不是重复数为止

//
    /*

public class Num82_deleteDuplicates {
    public ListNode deleteDuplicates(ListNode head){

        // //当链表为空或者 只有一个是时候，肯定没有重复元素
        if(head == null || head.next == null){
            return head;
        }
        //此时说明至少有两个节点，可能存在重复数
        ListNode dummyHead = new ListNode();//虚拟头节点
        dummyHead.next = head;//连接一下
        ListNode prve = dummyHead;//前驱
        ListNode node1 = prve.next;//遇到重复数保持不动
        ListNode node2 = node1.next;//每次向后移动
        while(node2 != null){
            if(node1.val == node2.val){
                //说明此时两个节点都是要被删除的
                while(node2 != null && node1.val == node2.val){
                    node2 = node2.next;
                }//走到不是刚遇到的重复数的时候停下来
                prve.next = node2;//更新前驱节点保存的地址
                //判断一下node2是否走到头了
                if(node2 == null)
                    return dummyHead.next;
            }else{
                //如果他们都不是重复的数
                //移动prve的位置
                prve = prve.next;
            }
            node1 = node2;
            node2 = node2.next;
        }
        return dummyHead.next;
    }
}

     */

/**
 * 递归写法：功能是删除链表里面所有重复的元素，返回新链表的头
 */

/**
 * 思路：我们要做的是 必须保证头节点不是待删除元素，然后把头节点不是待删除链表
 * 交给子方法去处理，让它完成里面的重复删除。
 */
public class Num82_deleteDuplicates {

    public ListNode deleteDuplicates(ListNode head) {

        //什么情况下不用删除了？
        if(head == null || head.next == null){
            //为空，或者只有一个节点，那肯定没有重复数啊
            return head;
        }
        //判断头节点是否是待删除节点
        if(head.val != head.next.val){
            head.next = deleteDuplicates(head.next);
            return head;//因为第一个不是待删除节点，所以可以直接连接
        }else{
            //重点！如果是带删除节点的话 ，先处理掉
            //注释：我们只需要做到删除头节点带删数，至于后面的数里面有没有头节点交给方法去执行
            ListNode node = head.next;
            while(node != null && head.val == node.val){
                //重复的话就一直让node往后走
                node = node.next;
            }//循环完后node跟第一个头节点val相比，肯定不相同。
            //node是新的头节点，至于这个头节点是否需要删除，就交给子方法
            return deleteDuplicates(node);

        }
    }
}

